package tree.interator;

import tree.TreeNode;
import tree.recurrence.InOrder;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName PreOrder
 * @Description TODO
 * @Author lenovo
 * @Date 2023-03-08 10:00
 * @Version 1.0
 * @Comment Magic. Do not touch.
 * If this comment is removed. the program will blow up
 */
public class PreOrder {

    public List<Integer> PreOrder(TreeNode treeNode) {

        List<Integer> res = new ArrayList<>();
        if (treeNode == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();

        stack.push(treeNode);

        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            res.add(pop.val);

            if (pop.right != null) {
                stack.push(pop.right);
            }

            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
        return res;
    }

    //      2
    //    1   3
    public List<Integer> inOrder(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                res.add(cur.val);
                cur = cur.right;
            }
        }

        return res;
    }


    public static void main(String[] args) {
        PreOrder preOrder = new PreOrder();

        TreeNode treeNode = new TreeNode(2);

        TreeNode treeNodeLeft = new TreeNode(1);
        treeNode.left = treeNodeLeft;

        TreeNode treeNodeRight = new TreeNode(3);
        treeNode.right = treeNodeRight;


        List<Integer> list = preOrder.inOrder(treeNode);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

    }
}